package com.cuz.daileetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @description: 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,3]
 * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 * 示例 2：
 *
 * 输入：nums = [0,1]
 * 输出：[[0,1],[1,0]]
 * 示例 3：
 *
 * 输入：nums = [1]
 * 输出：[[1]]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/permutations
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author cuzz
 * @date 22:41 2021/9/22
 * @version 1.0
 **/
public class Day5_2 {
    /**
     * @description: 经典回溯
     *
     * 递归找到所有解
     * 剪枝条件1：所有可能的全排列  排列的数目等于nums长度，
     * 剪枝条件2：不含重复数字的数组 so 递归数的第n层不包含n-1所有子节点的数
     *
     * 1.首先 要记录每一个数是否倍使用1，可以使用hashmap
     * 也可以使用数组 memory对应下标的值标记是否被使用 0未使用，1使用
     *
     * 回溯通用模板:
     * 1.递归出口:当前结果包含全部数 返回
     * 2.递归到下一层 剪枝（标记当这个数被使用了）加入到临时结果 继续进入到下一层
     * 3.回溯 删除最好一个数 标记未使用
     *
     * 举例子：
     * 1，2，3，
     * 初始化 res=[]  memory[0.0,0] singleRes=[]
     *                     S
     *第 1层        1       2       3     S=>3 res=[]  memory[0,0,1] singleRes=[3]
     * 第 2层     2   3    1  3    1   2   S=>3=>2 res=[]  memory[0,1，1] singleRes=[3,2]
     * 第 3层     3     2  3    1   2     1   S=>3=>2 =>1  res=[[3,2,1]]  memory[1,1，1] singleRes=[3,2,1] 递归出口 res加入singleRes
     *
     *                                 回溯 第三层到 第二层   memory[0,1，1] singleRes=[3,2]
     *                                 回溯 第2层到 第1层   memory[0,0，1] singleRes=[3]
     *                                 回溯 第2层到 第0层   memory[0,0，0] singleRes=[]
     *
     *                                 继续递归 1，2，作为开头
     *
     *
      * @author cuzz
     * @date 23:01 2021/9/22
     * @version 1.0
     **/
    class S1{
        public List<List<Integer>> permute(int[] nums) {
            List<List<Integer>> res=new ArrayList<>();
            int[]memory=new int[nums.length];
            backTrack(nums,res,new LinkedList<>(),memory);
            return res;
        }
        private void backTrack(int[] nums, List<List<Integer>> res, LinkedList<Integer> singleRes, int[]memory){
            if (singleRes.size()==nums.length){
                ArrayList<Integer> temp = new ArrayList<>(singleRes);
                res.add(temp);
                return;
            }
            for (int index = 0; index < nums.length; index++) {
                int tempNum=nums[index];
                //0未使用，1使用
                if (memory[index]==0){
                    memory[index]=1;
                    singleRes.add(tempNum);
                    backTrack(nums, res, singleRes, memory);
                    singleRes.removeLast();
                    memory[index]=0;
                }
            }
        }

    }
}
